DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2024.17

Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability

Authors: Nicolás Bitar

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract

We study the seeded domino problem, the recurring domino problem and the k-SAT problem on finitely generated groups. These problems are generalization of their original versions on ℤ² that were shown to be undecidable using the domino problem. We show that the seeded and recurring domino problems on a group are invariant under changes in the generating set, are many-one reduced from the respective problems on subgroups, and are positive equivalent to the problems on finite index subgroups. This leads to showing that the recurring domino problem is decidable for free groups. Coupled with the invariance properties, we conjecture that the only groups in which the seeded and recurring domino problems are decidable are virtually free groups. In the case of the k-SAT problem, we introduce a new generalization that is compatible with decision problems on finitely generated groups. We show that the subgroup membership problem many-one reduces to the 2-SAT problem, that in certain cases the k-SAT problem many one reduces to the domino problem, and finally that the domino problem reduces to 3-SAT for the class of scalable groups.

Cite as

Nicolás Bitar. Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bitar:LIPIcs.STACS.2024.17,
  author =	{Bitar, Nicol\'{a}s},
  title =	{{Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.17},
  URN =		{urn:nbn:de:0030-drops-197275},
  doi =		{10.4230/LIPIcs.STACS.2024.17},
  annote =	{Keywords: Tilings, Domino problem, SAT, Computability, Finitely generated groups}
}

Search Results

Documents authored by Bitar, Nicolás

Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability

Abstract

Cite as

Thanks for your feedback!

Could not send message